検索とソート：大量データ処理の基盤

検索とソートはアルゴリズムの入門であるばかりでなく、コンピュータサイエンスにおけるデータ処理の根本的な論理です。データの価値は、その検索や整理の効率にかかっています。本節では最も基本的な線形探索アルゴリズム評価の核心を明らかにします——すなわち、異なるデータ構造において、どのように線形比較によってターゲットを特定するかという点です。

1. ロジックとコスト

線形探索：リストの最初の要素から始め、デフォルトの順序に沿って順番に確認し、ターゲット要素が見つかるか、リストの末尾まで確認するまで続けます。時間計算量は $O(n)$です。

2. 比較：無順序対順序

において無順序リストでは（下表参照）、成功・失敗に関わらず、平均的な比較回数は通常 $n$ と比例します。一方、順序リストでは、データの並び順の規則を利用することで「早期終了」が可能になります：ターゲット値より大きな要素に遭遇した時点で、ターゲットが存在しないと判断できます。これにより $O(n)$ の本質は変わりませんが、失敗時の平均効率が向上します。